Many current mid to high-end data processing systems employ storage systems that comprise arrays of small form factor direct access storage devices such as magnetic disk drives. Such arrays are designed to emulate large form factor devices while offering the advantages of lower cost, smaller size, improved performance and reduced power consumption. A number of alternative array architectures have been developed to achieve good overall array reliability; one of which is RAID (Redundant Array of Independent Disks) defined by the RAID advisory board and which includes a number of variants (commonly called ‘levels’). One commonly used variant is RAID 5 in which a data stripe consists of a number of data strips and a parity strip, each strip being stored on one member disk of the array. In RAID 5 the parity strips of different data stripes are distributed across the member disks. Further details of RAID 5 and the other variants may be found in the ‘RAID book’ (ISBN 1-57398-028-5).
A more recently developed array architecture is the Log Structured Array (LSA) in which the Log Structured Filesystem (LSF) approach, pioneered at the University of California Berkeley, is combined with RAID. Examples of systems employing the LSA architecture are described in U.S. Pat. Nos. 5,124,987 and 5,671,390. LSA is most often described as being implemented using RAID 5 techniques.
An LSA consists of a disk controller and N+1 physical disks. In an LSA, data is stored on disks in compressed form. After a piece of data is updated, it may not compress to the same size as it did before it was updated, so it may not fit back into the space that had been allocated for it before the update. The implication is that there can no longer be fixed, static locations for all the data. An LSA controller manages information storage to write updated data into new disk locations rather than writing new data in place. Therefore, the LSA must keep a directory which it uses to locate data items in the array.
As an illustration of the N+1 physical disks, an LSA can be considered as consisting of a group of disk drive DASDs, each of which includes multiple disk platters stacked into a column. Each disk is divided into large consecutive areas called segment-columns. A segment-column is typically as large as a physical cylinder on a physical disk. Corresponding segment-columns from the N+1 disks constitute a segment. The array has as many segments as there are segment-columns on a disk in the array. One of the segment-columns of a segment contains the parity (exclusive-OR) of the remaining segment-columns of the segment. For performance reasons, the parity segment-columns are not all on the same disk, but are rotated among the disks.
Logical devices are mapped and stored in the LSA. A logical track is stored, as a set of compressed records, entirely within some segment of the LSA; many logical tracks can be stored in the same segment. The location of a logical track in an LSA changes over time. A directory, called the LSA directory, indicates the current location of each logical track. The LSA directory is maintained either in Non-Volatile Storage (NVS) or paged virtual memory in the disk controller.
Reading and writing into an LSA occurs under management of the LSA controller. An LSA controller can include resident microcode that emulates logical devices such as direct access storage device (DASD) disk drives, or tape drives. In this way, the physical nature of the external storage subsystem can be transparent to the operating system and to the applications executing on the computer processor accessing the LSA. Thus, read and write commands sent by the computer processor to the external information storage system would be interpreted by the LSA controller and mapped to the appropriate disk storage locations in a manner not known to the computer processor. This comprises a mapping of the LSA logical devices onto the actual disks of the LSA.
A write received from the host system is first written into a non-volatile cache and the host is immediately notified that the write is done. The fraction of cache occupied by modified logical tracks is monitored by the controller. When this fraction exceeds some threshold, some number of modified logical tracks are moved (logically) to a memory segment, from where they get written (destaged) to disk. The memory segment is a section of controller memory, logically organized as N+1 segment-columns called memory segment-columns; N data memory segment-columns and 1 parity memory segment-column. When all or part of a logical track is selected from the NVS, the entire logical track is written into one of the N data memory segment-columns. When all data memory segment-columns are full, an XOR operation is applied to all the data memory segment-columns to create the parity memory segment-column, then all N+1 memory segment-columns are written to an empty segment on the disk array. It is important for the performance of LSA that a segment is an integral number of RAID 5 stripes so that parity can be calculated over the destaged data without reading the old data and parity and so incurring the RAID 5 write penalty.
All logical tracks that were just written to disk from the memory segment must have their entries in the LSA directory updated to reflect their new disk locations. If these logical tracks had been written before by the system, the LSA directory would have contained their previous physical disk locations; otherwise the LSA directory would have indicated that the logical track had never been written, and consequently has no address. Note that writing to the disk is more efficient in LSA than in RAID-5, where 4 disk accesses are needed for an update.
In Log Structured Arrays, data to be written is grouped together into relatively large blocks (the segments) which are written out as a unit in a convenient free segment location on disk. When data is written, the previous disk locations of the data become free creating “holes” of unused data (or garbage) in the segments on disk. Eventually the disk fills up with segments and it is necessary to create free segment locations by reading source segments with holes and compacting their still-in-use content into a lesser number of destination segments without holes. This process is called free space or garbage collection.
When the user of a non-LSA RAID array wishes to expand the storage capacity of the array, one option is to add one or more new member disk drives to the array. In RAID 5 arrays, the problem arises as to how to remap the data and/or parity whilst adding one or more disks. Furthermore a number of characteristics are important for any RAID array expansion scheme: (i) host IOs should not be held off for long periods of time; (ii) the amount of data/parity that needs to be moved should be minimised; and (iii) the translation of logical address to physical address should be kept as simple as possible since this calculation must be performed for every array IO access. A number of patents including U.S. Pat. Nos. 5,502,836, 5,524,204, 5,615,352 and 5,758,118 address the aforementioned problem and seek to trade off these desirable characteristics.
Expansion capability for log structured arrays is also desirable. One relatively straight forward way of doing this would be to add a complete new RAID array to the log-structured array, as a log structured array may consist of one or more RAID arrays. However, the LSA user may not need all the additional storage capacity provided by an additional RAID array and therefore it would often be preferable to increase storage capacity by adding one or more member disk drives to a RAID array which is already a member of an LSA. However, a number of additional problems arise in adding new members to a RAID array that forms part is of an LSA, none of which are addressed in the prior art. These are: (i) LSA performance is tied to the ability to perform full stripe writes for destaging segment sized IOs to the array. Thus the logical block addresses of the blocks in a stripe after the array expansion must be sequential; (ii) since the LSA segment size is tied to the array stripe size, if this changes, the segment size for new destages must change to match; and (iii) since LSA obtains new segments for filling by employing a garbage collection algorithm over previously destaged segments, it is convenient that newly destaged segments are the same size as pre-existing segments.
It would be desirable to provide an improved expansion/contraction scheme for an information storage system configured as a log structured array.